//什么是递归？
//程序调用自身的编程技巧称为递归（recursion）。递归做为一种算法在程序设计语言中广泛应用。
// 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，
// 递归策略只需少量的程序就可以描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。  
// 递归的主要思考方式在于：把大事化小           写递归，最重要的就是考虑那个终止条件和循环条件
/*注意写递归代码的时候：
1.不能死递归，都有跳出条件，每次递归逼近跳出条件
2.递归层次不能太深  */ 
//例一：接受一个整型值（无符号，按照顺序打印它的每一位。例如：输入：1234，输出1 2 3 4
/*	1234 % 10 =              4
	1234 / 10 = 123 % 10 = 3
	123 / 10 = 12 % 10 = 2
	12 / 10 = 1 % 10 = 1   
	1 /  10 = 0
	*/
//递归怎么做？ 
/*	print(1234)
	print(123) 4
	print(12) 3 4
	print(1) 2 3 4    */  
	
void print(unsigned int n) 
{
	if (n > 9) { //即一位s数 以上的数字时  ！！！ 递归要有条件，避免死递归
		/* 递归的两个必要条件：
			1.存在限制条件，当满足这个限制条件的时候，递归便不再继续。
			2.每次递归调用之后越来越接近这个限制条件。    同时也要避免多次递归 因栈区空间挺小的。溢出出错。*/
		print(n / 10);
	}
	printf("%d ", n % 10);  //10以内的数字 除10模10都一样
}
int main() {
	unsigned int num = 0;  //unsigned是无符号型
	scanf("%d", &num); //1234
	//递归-函数自己调自己
	print(num); //print函数可以打印参数部分数字的每一位
		
	return 0;

}


//例二.编写函数不允许创建临时变量 求字符串的长度。
int my_strlen(char* str)
{ 
	//常规写法：
	//int count = 0; //创建了临时变量
	//while(*str != '\0')
	//{
	//	count++;
	//	str++;
	//}
	//return count;

	//递归写法：  大事化小
/*	my_strlen("bit") :
	1 + my_strlen("it")
	1 + l + my_strlen("t"）
	1 + 1 + l + my_strlen("）
	1 + 1 + 1 + 0 = 3          */
	if (*str !='\0')
	{
		return 1 + my_strlen(str + 1);
	}
	else
	{
		return 0;
	}
}
int main() {
	char arr[] = "bit";
	//['b']['i']['t']['\0']
	//模拟实现一个strlen函数
	printf("%d", my_strlen(arr));
	return 0;
}

/练习3：求n的阶乘。（不考虑溢出）
//递归方式：
int Fac(int n) {
	if (n <= 1) {
		return 1;
	}
	else
	{
		return n * Fac(n - 1);
	}
}
int main() 
{
	int n = 0;
	scanf("%d",&n);
	//常规写法：
	//int i = 0;
	//int ret = 1;
	////循环是一种迭代
	//for ( i = 1; i <= n; i++)
	//{
	//	ret = ret * i;
	//}
	//printf("%d\n", ret);
	int ret = Fac(n);
	printf("%d\n", ret);
	return 0;
}

/练习4：求n个斐波那契数。(不考虑溢出)
// 1 1 2 3 5 8 13 21 34 55... 

int  Fib(int n) {
	//1.递归方式：按公式算 进行了重复大量的计算 程序效率太低了!   (这里层次不深，调用次数多，所以没栈溢出)
	//if (n<=2)
	//{
	//	return 1;
	//}
	//else
	//{
	//	return Fib(n - 1) + Fib(n - 2);
	//}
	//2.循环（迭代）方式：  c=a+b;        （第50个后面的 超出了整型的范围 所以结果时错的）
	int a = 1;
	int b = 1;
	int c = 1; 
	//int a=1,b=1,b=1;   简写  （赋初值）
	while (n>2) { //3个斐波那契数时 开始算
		c = a + b;
		a = b;
		b = c;
		n--; //每循环一次 就接近n值  （算一次 减少一次）
	}
	return c;
}
int main() {
	int  n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;

}